P3327 [SDOI2015]约数个数和

首先有一个公式：

$d(ij)=\sum_{x|i}\sum_{y|j}[(i,j)=1]$

感性理解一下，可以看看这位大佬的博客。

那么:

$\sum_{i=1}^n\sum_{j=1}^md(ij)$

$\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[(x,y)=1]$

改为枚举约数，得：

$\sum_{x=1}^n\sum_{y=1}^m \lfloor \frac{n}{x} \rfloor \lfloor \frac{m}{y} \rfloor [(x,y)=1]$

$\sum_{x=1}^n\sum_{y=1}^m \lfloor \frac{n}{x} \rfloor \lfloor \frac{m}{y} \rfloor \sum_{d|(x,y)} \mu(d)$

$\sum_{d=1}^{\min(n,m)} \mu(d) \sum_{x=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{y=1}^{\lfloor \frac{m}{d} \rfloor} \lfloor \frac{n}{dx} \rfloor \lfloor \frac{m}{dy} \rfloor$

$\sum_{d=1}^{\min(n,m)} \mu(d) \sum_{x=1}^{\lfloor \frac{n}{d} \rfloor} \lfloor \frac{n}{dx} \rfloor \sum_{y=1}^{\lfloor \frac{m}{d} \rfloor } \lfloor \frac{m}{dy} \rfloor$

令 $f(x)=\sum_{i=1}^x \lfloor \frac{x}{i} \rfloor$ ，则原式为

$\sum_{d=1}^{\min(n,m)} \mu(d) f( \lfloor \frac{n}{d} \rfloor ) f( \lfloor \frac{m}{d} \rfloor )$

再看看 $f(x)$ ，其实就是约数个数的前缀和，原因很简单：

$f(x)$ 表示不大于 $x$ 的数的倍数不大于 $x$ 的数的个数。

$d(x)$ 表示不大于 $x$ 的数的倍数为 $x$ 的数的个数。

可以欧拉筛约数个数再前缀和得到，那么此题就解决了。

时间复杂度 $\Theta(n+t\sqrt n)$。

#include <cstdio>
#include <iostream>
using namespace std;

const int MAXN = 50000;
int t , n , m , k , prime[ MAXN + 5 ];
int mu[ MAXN + 5 ] , d[ MAXN + 5 ] , f[ MAXN + 5 ] , pre_mu[ MAXN + 5 ];
bool vis[ MAXN + 5 ];

void sieve( ) {
	mu[ 1 ] = 1 , d[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ ) {
		if( !vis[ i ] ) {
			prime[ ++ k ] = i;
			mu[ i ] = -1;
			d[ i ] = 2;
		}
		for( int j = 1 ; j <= k && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
			vis[ i * prime[ j ] ] = 1;
			if( i % prime[ j ] == 0 ) {
				d[ i * prime[ j ] ] = 2 * d[ i ] - d[ i / prime[ j ] ];
				break;
			}
			mu[ i * prime[ j ] ] = -mu[ i ];
			d[ i * prime[ j ] ] = d[ i ] * d[ prime[ j ] ];
		}
	}
	for( int i = 1 ; i <= MAXN ; i ++ ) {
		f[ i ] = f[ i - 1 ] + d[ i ];
		pre_mu[ i ] = pre_mu[ i - 1 ] + mu[ i ];
	}
}

long long solve( int n , int m ) {
	int d = min( n , m );
	long long Ans = 0;
	for( int l = 1 , r ; l <= d ; l = r + 1 ) {
		r = min( n / ( n / l ) , m / ( m / l ) );
		Ans += 1ll * ( pre_mu[ r ] - pre_mu[ l - 1 ] ) * f[ n / l ] * f[ m / l ];
	}
	return Ans;
}
int main( ) {
	sieve( );
	scanf("%d",&t);
	while( t -- ) {
		scanf("%d %d",&n,&m);
		printf("%lld\n", solve( n , m ) );
	}
	return 0;
}